<!DOCTYPE HTML>
<html lang="zh-CN">


<head>
    <meta charset="utf-8">
    <meta name="keywords" content="数学建模算法2-整数规划, python,machine learning,deep learning,html,css,c,c++,cpp,cmake,ros,linux,ubuntu">
    <meta name="description" content="本文主要讲解了数学建模中常见的一类问题：整数规划，及其求解">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=no">
    <meta name="renderer" content="webkit|ie-stand|ie-comp">
    <meta name="mobile-web-app-capable" content="yes">
    <meta name="format-detection" content="telephone=no">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black-translucent">
    <meta name="referrer" content="no-referrer-when-downgrade">
    <!-- Global site tag (gtag.js) - Google Analytics -->


    <title>数学建模算法2-整数规划 | JackWang&#39;s Blog</title>
    <link rel="icon" type="image/png" href="/favicon.png">

    <link rel="stylesheet" type="text/css" href="/libs/awesome/css/all.min.css">
    <link rel="stylesheet" type="text/css" href="/libs/materialize/materialize.min.css">
    <link rel="stylesheet" type="text/css" href="/libs/aos/aos.css">
    <link rel="stylesheet" type="text/css" href="/libs/animate/animate.min.css">
    <link rel="stylesheet" type="text/css" href="/libs/lightGallery/css/lightgallery.min.css">
    <link rel="stylesheet" type="text/css" href="/css/matery.css">
    <link rel="stylesheet" type="text/css" href="/css/my.css">

    <script src="/libs/jquery/jquery-3.6.0.min.js"></script>

<meta name="generator" content="Hexo 5.4.2">
<style>.github-emoji { position: relative; display: inline-block; width: 1.2em; min-height: 1.2em; overflow: hidden; vertical-align: top; color: transparent; }  .github-emoji > span { position: relative; z-index: 10; }  .github-emoji img, .github-emoji .fancybox { margin: 0 !important; padding: 0 !important; border: none !important; outline: none !important; text-decoration: none !important; user-select: none !important; cursor: auto !important; }  .github-emoji img { height: 1.2em !important; width: 1.2em !important; position: absolute !important; left: 50% !important; top: 50% !important; transform: translate(-50%, -50%) !important; user-select: none !important; cursor: auto !important; } .github-emoji-fallback { color: inherit; } .github-emoji-fallback img { opacity: 0 !important; }</style>
<link rel="stylesheet" href="/css/prism-tomorrow.css" type="text/css">
<link rel="stylesheet" href="/css/prism-line-numbers.css" type="text/css"></head>



   <style>
    body{
       background-image: url(https://cdn.jsdelivr.net/gh/Tokisaki-Galaxy/res/site/medias/background.jpg);
       background-repeat:no-repeat;
       background-size: 100% 100%;
       background-attachment:fixed;
    }
</style>



<body>
    <header class="navbar-fixed">
    <nav id="headNav" class="bg-color nav-transparent">
        <div id="navContainer" class="nav-wrapper container">
            <div class="brand-logo">
                <a href="/" class="waves-effect waves-light">
                    
                    <img src="/medias/logo.png" class="logo-img" alt="LOGO">
                    
                    <span class="logo-span">JackWang&#39;s Blog</span>
                </a>
            </div>
            

<a href="#" data-target="mobile-nav" class="sidenav-trigger button-collapse"><i class="fas fa-bars"></i></a>
<ul class="right nav-menu">
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="/" class="waves-effect waves-light">
      
      <i class="fas fa-home" style="zoom: 0.6;"></i>
      
      <span>首页</span>
    </a>
    
  </li>
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="" class="waves-effect waves-light">

      
      <i class="fas fa-book-reader" style="zoom: 0.6;"></i>
      
      <span>博客</span>
      <i class="fas fa-chevron-down" aria-hidden="true" style="zoom: 0.6;"></i>
    </a>
    <ul class="sub-nav menus_item_child ">
      
      <li>
        <a href="/tags">
          
          <i class="fas fa-tags" style="margin-top: -20px; zoom: 0.6;"></i>
          
	  <span>按标签归类文章</span>
        </a>
      </li>
      
      <li>
        <a href="/categories">
          
          <i class="fas fa-bookmark" style="margin-top: -20px; zoom: 0.6;"></i>
          
	  <span>按目录归类文章</span>
        </a>
      </li>
      
      <li>
        <a href="/archives">
          
          <i class="fas fa-archive" style="margin-top: -20px; zoom: 0.6;"></i>
          
	  <span>按日期分类文章</span>
        </a>
      </li>
      
    </ul>
    
  </li>
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="/about" class="waves-effect waves-light">
      
      <i class="fas fa-user-circle" style="zoom: 0.6;"></i>
      
      <span>关于</span>
    </a>
    
  </li>
  
  <li>
    <a href="#searchModal" class="modal-trigger waves-effect waves-light">
      <i id="searchIcon" class="fas fa-search" title="搜索" style="zoom: 0.85;"></i>
    </a>
  </li>
</ul>



<div id="mobile-nav" class="side-nav sidenav">

    <div class="mobile-head bg-color">
        
        <img src="/medias/logo.png" class="logo-img circle responsive-img">
        
        <div class="logo-name">JackWang&#39;s Blog</div>
        <div class="logo-desc">
            
            JackWang的个人博客
            
        </div>
    </div>

    <ul class="menu-list mobile-menu-list">
        
        <li class="m-nav-item">
	  
		<a href="/" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-home"></i>
			
			首页
		</a>
          
        </li>
        
        <li class="m-nav-item">
	  
		<a href="javascript:;">
			
				<i class="fa-fw fas fa-book-reader"></i>
			
			博客
			<span class="m-icon"><i class="fas fa-chevron-right"></i></span>
		</a>
            <ul  style="background:  ;" >
              
                <li>

                  <a href="/tags " style="margin-left:75px">
				  
				   <i class="fa fas fa-tags" style="position: absolute;left:50px" ></i>
			      
                              <span>按标签归类文章</    span>

                  </a>
                </li>
              
                <li>

                  <a href="/categories " style="margin-left:75px">
				  
				   <i class="fa fas fa-bookmark" style="position: absolute;left:50px" ></i>
			      
                              <span>按目录归类文章</    span>

                  </a>
                </li>
              
                <li>

                  <a href="/archives " style="margin-left:75px">
				  
				   <i class="fa fas fa-archive" style="position: absolute;left:50px" ></i>
			      
                              <span>按日期分类文章</    span>

                  </a>
                </li>
              
            </ul>
          
        </li>
        
        <li class="m-nav-item">
	  
		<a href="/about" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-user-circle"></i>
			
			关于
		</a>
          
        </li>
        
        
    </ul>
</div>


        </div>

        
    </nav>

</header>

    
<script src="/libs/cryptojs/crypto-js.min.js"></script>
<script>
    (function() {
        let pwd = '';
        if (pwd && pwd.length > 0) {
            if (pwd !== CryptoJS.SHA256(prompt('抱歉，这篇文章并不想让所有人都看到，请输入授权密码观看')).toString(CryptoJS.enc.Hex)) {
                alert('密码错误，将返回主页！');
                location.href = '/';
            }
        }
    })();
</script>




<div class="bg-cover pd-header post-cover" style="background-image: url('https://jack-1307599355.cos.ap-shanghai.myqcloud.com/img/2305037-20210603134210658-726109005.png')">
    <div class="container" style="right: 0px;left: 0px;">
        <div class="row">
            <div class="col s12 m12 l12">
                <div class="brand">
                    <h1 class="description center-align post-title">数学建模算法2-整数规划</h1>
                </div>
            </div>
        </div>
    </div>
</div>




<main class="post-container content">

    
    <link rel="stylesheet" href="/libs/tocbot/tocbot.css">
<style>
    #articleContent h1::before,
    #articleContent h2::before,
    #articleContent h3::before,
    #articleContent h4::before,
    #articleContent h5::before,
    #articleContent h6::before {
        display: block;
        content: " ";
        height: 100px;
        margin-top: -100px;
        visibility: hidden;
    }

    #articleContent :focus {
        outline: none;
    }

    .toc-fixed {
        position: fixed;
        top: 64px;
    }

    .toc-widget {
        width: 345px;
        padding-left: 20px;
    }

    .toc-widget .toc-title {
        padding: 35px 0 15px 17px;
        font-size: 1.5rem;
        font-weight: bold;
        line-height: 1.5rem;
    }

    .toc-widget ol {
        padding: 0;
        list-style: none;
    }

    #toc-content {
        padding-bottom: 30px;
        overflow: auto;
    }

    #toc-content ol {
        padding-left: 10px;
    }

    #toc-content ol li {
        padding-left: 10px;
    }

    #toc-content .toc-link:hover {
        color: #42b983;
        font-weight: 700;
        text-decoration: underline;
    }

    #toc-content .toc-link::before {
        background-color: transparent;
        max-height: 25px;

        position: absolute;
        right: 23.5vw;
        display: block;
    }

    #toc-content .is-active-link {
        color: #42b983;
    }

    #floating-toc-btn {
        position: fixed;
        right: 15px;
        bottom: 76px;
        padding-top: 15px;
        margin-bottom: 0;
        z-index: 998;
    }

    #floating-toc-btn .btn-floating {
        width: 48px;
        height: 48px;
    }

    #floating-toc-btn .btn-floating i {
        line-height: 48px;
        font-size: 1.4rem;
    }
</style>
<div class="row">
    <div id="main-content" class="col s12 m12 l9">
        <!-- 文章内容详情 -->
<div id="artDetail">
    <div class="card">
        <div class="card-content article-info">
            <div class="row tag-cate">
                <div class="col s7">
                    
                    <div class="article-tag">
                        
                            <a href="/tags/Python/">
                                <span class="chip bg-color">Python</span>
                            </a>
                        
                            <a href="/tags/Math-Modeling/">
                                <span class="chip bg-color">Math Modeling</span>
                            </a>
                        
                            <a href="/tags/Linear-Programming/">
                                <span class="chip bg-color">Linear Programming</span>
                            </a>
                        
                            <a href="/tags/%E6%95%B4%E6%95%B0%E8%A7%84%E5%88%92/">
                                <span class="chip bg-color">整数规划</span>
                            </a>
                        
                    </div>
                    
                </div>
                <div class="col s5 right-align">
                    
                    <div class="post-cate">
                        <i class="fas fa-bookmark fa-fw icon-category"></i>
                        
                            <a href="/categories/%E6%95%B0%E5%AD%A6%E5%BB%BA%E6%A8%A1%E7%AE%97%E6%B3%95/" class="post-category">
                                数学建模算法
                            </a>
                        
                    </div>
                    
                </div>
            </div>

            <div class="post-info">
                
                <div class="post-date info-break-policy">
                    <i class="far fa-calendar-minus fa-fw"></i>发布日期:&nbsp;&nbsp;
                    2022-01-02
                </div>
                

                
                <div class="post-date info-break-policy">
                    <i class="far fa-calendar-check fa-fw"></i>更新日期:&nbsp;&nbsp;
                    2023-06-01
                </div>
                

                
                <div class="info-break-policy">
                    <i class="far fa-file-word fa-fw"></i>文章字数:&nbsp;&nbsp;
                    6.4k
                </div>
                

                
                <div class="info-break-policy">
                    <i class="far fa-clock fa-fw"></i>阅读时长:&nbsp;&nbsp;
                    26 分
                </div>
                

                
                    <div id="busuanzi_container_page_pv" class="info-break-policy">
                        <i class="far fa-eye fa-fw"></i>阅读次数:&nbsp;&nbsp;
                        <span id="busuanzi_value_page_pv"></span>
                    </div>
				
            </div>
        </div>
        <hr class="clearfix">

        

        

        <div class="card-content article-card-content">
            <div id="articleContent">
                <blockquote>
<p>本文主要讲解了数学建模中常见的一类问题：整数规划，及其求解</p>
</blockquote>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/img/2305037-20210603134210658-726109005.png" alt="整数规划"></p>
<h1 id="数学建模算法2-整数规划"><a href="#数学建模算法2-整数规划" class="headerlink" title="数学建模算法2-整数规划"></a>数学建模算法2-整数规划</h1><p>在上一篇文章中，我们介绍了线性规划问题及其算法求解。线性规划问题的关键就在于：</p>
<ol>
<li>有限的资源（写出来约束）</li>
<li>最大化价值（写出来目标函数）</li>
</ol>
<p>判断一个问题是否可以通过线性规划求解就是看这个问题是否通过划归而具有上面的两个特点。</p>
<p>线性规划其实有一个隐含的条件，就是要求决策变量（需要通过线性规划决策值的变量）是连续的。但是在现实中，并不所有线性规划问题的决策变量都是连续的，有的时候，我们的决策变量是一个整数。</p>
<p>例如任务指派问题，在有限的人数的情况下尽可能少的派人去完成问题，这个问题符合上面的两个特点。但是其决策变量人数并不是一个连续的变量，因此直接套用线性规划是不行的。那么可能就会有人要问了，线性规划给出的小数解可能不符合要求，那么取整不就可以了？</p>
<p>但其实简单的取整是不能处理所有的这样的问题的，例如封面图：线性规划给出的最优解是右侧的点，对这个点的x、y坐标无论怎样取整，得到的解都不在可行域内，甚至周围几个点也都不在可行域内。因此针对这类问题我们为他们取了一个名字：<strong>整数规划（Integer Programming，IP）</strong>，并对整数问题的求解方法进行研究。</p>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/img/2305037-20210603134210658-726109005.png" alt="整数规划"></p>
<h2 id="1-整数规划的发展历史"><a href="#1-整数规划的发展历史" class="headerlink" title="1. 整数规划的发展历史"></a>1. 整数规划的发展历史</h2><p>上面的lead-in其实已经相当于介绍了，那么这里就介绍一下整数规划的发展历史吧。</p>
<p>整数规划是从1958年由R.E.戈莫里提出线性规划的割平面法之后形成独立分支的 ，30多年来发展出很多方法解决各种问题。解整数规划最典型的做法是逐步生成一个相关的问题，称它是原问题的衍生问题。对每个衍生问题又伴随一个比它更易于求解的松弛问题（衍生问题称为松弛问题的源问题）。通过松弛问题的解来确定它的源问题的归宿，即源问题应被舍弃，还是再生成一个或多个它本身的衍生问题来替代它。随即 ，再选择一个尚未被舍弃的或替代的原问题的衍生问题，重复以上步骤直至不再剩有未解决的衍生问题为止。现今比较成功又流行的方法是<strong>分支定界法</strong>和<strong>割平面法</strong>，它们都是在上述框架下形成的。 </p>
<p><strong>需要注意的是，目前对于整数规划并不存在求解一切整数规划问题的方法（二次的约束、不连续的约束），目前流行的求解方法往往只适用于线性整数规划</strong></p>
<h2 id="2-整数规划的定义"><a href="#2-整数规划的定义" class="headerlink" title="2. 整数规划的定义"></a>2. 整数规划的定义</h2><p>通过上面的介绍，我们应该明白了什么是整数规划，即决策变量是整数的规划问题。<strong>如果规划的约束和目标函数都是线性的话，则称为线性整数规划</strong>。考虑到我们在数学建模的过程中往往都是对线性整数规划进行的求解，因此<strong>我们也把线性整数规划简称为整数规划</strong>，并且在<strong>后文中如果我们没有特地声明，那么所说的整数规划统统指线性整数规划</strong></p>
<p>上面是我们主观的理解，下面给出百度百科和维基百科上的定义：</p>
<blockquote>
<p><strong>From BaiduBaike</strong>：</p>
<p>整数规划是指规划中的变量（全部或部分）限制为整数，若在线性模型中，变量限制为整数，则称为整数线性规划。所流行的求解整数规划的方法往往只适用于整数线性规划。<br>一类要求问题的解中的全部或一部分变量为整数的数学规划。从约束条件的构成又可细分为线性，二次和非线性的整数规划。 </p>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/img/image-20220102015830244.png" alt="百度百科对整数规划的介绍"></p>
<p><strong>From Wikipedia</strong>：</p>
<p>PS: 维基百科没有针对整数规划的词条。整数规划的定义在线性规划词条下。</p>
<p>要求所有的未知量都为整数的线性规划问题叫做<strong>整数规划</strong>（integer programming, IP）或<strong>整数线性规划</strong>（integer linear programming, ILP）问题。</p>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/img/image-20220102020123747.png" alt="维基百科对整数规划的介绍"></p>
</blockquote>
<h2 id="3-整数规划的分类"><a href="#3-整数规划的分类" class="headerlink" title="3. 整数规划的分类"></a>3. 整数规划的分类</h2><p>针对问题中决策变量的不同，整数规划可以分为下面的几类：</p>
<ul>
<li><strong>纯整数规划（Pure Integer Programming，PIP）</strong>：所有的决策变量要求都是整数的整数规划，但是为解决问题引入的松弛变量或者剩余变量不要求取整</li>
</ul>
<blockquote>
<p><strong>松弛变量与剩余变量</strong>：</p>
<p>在求解多变量不等式问题的时候，通常形式是这样的：$x_1+x_2\leq 10$；有的时候为了便于求解，希望能够减少不等式中的变量个数。因此针对上式，引入第三个变量$x_3$，使得$x_1+x_2+x_3=10$，则原不等式变换为一个等式和一个单变量不等式$x_3\ge 0$。</p>
<p>此时称变量$x_3$为<strong>松弛变量</strong>。直观的理解就是$=$是更加严格的条件，而变量$x_3$让严格的条件松弛称为需要求解问题。</p>
<p>此外，若$x_1+x_2\ge 10$，则引入变量$x_3$，使得$x_1+x_2-x_3=10$，则$x_3\ge0$，此时称$x_3$为<strong>剩余变量</strong>。即比要求的$=10$多出来的部分</p>
</blockquote>
<ul>
<li><strong>混合整数规划（Mixed Integer Programming，MIP）</strong>：部分决策变量均要求为整数的整数规划</li>
<li><strong>纯0－1整数规划（Pure 0-1 Integer Programming）</strong>：所有决策变量均要求为0－1的整数规划</li>
<li><strong>混合0－1规划（Mixed 0-1 Integer Programming）</strong>：部分决策变量均要求为0－1的整数规划</li>
</ul>
<h2 id="4-整数规划和线性规划的关系"><a href="#4-整数规划和线性规划的关系" class="headerlink" title="4. 整数规划和线性规划的关系"></a>4. 整数规划和线性规划的关系</h2><h3 id="A-解之间的关系"><a href="#A-解之间的关系" class="headerlink" title="A. 解之间的关系"></a>A. 解之间的关系</h3><p>整数规划实际上是线性规划的一个特例，即在正常的线性规划上加上了非线性的整数约束。因此，根据线性规划解的特点，可以得到整数规划和线性规划解之间的关系：</p>
<ul>
<li><strong>最优解一致</strong>：<strong>整数规划去掉整数约束后的线性规划（称为伴随问题或者松弛问题）</strong>的最优解为整数，那么整数规划与线性规划的最优解一致。</li>
<li><strong>最优解变差</strong>：整数规划的伴随问题的最优解是小数，且整数规划存在可行解，那么整数规划的存在最优解，只是最优解相比伴随问题的最优解变差</li>
<li><strong>无最优解</strong>：伴随问题可行域内无整数解，故整数规划可能没有最优解</li>
</ul>
<h3 id="B-标准形式的关系"><a href="#B-标准形式的关系" class="headerlink" title="B. 标准形式的关系"></a>B. 标准形式的关系</h3><p>由于整数规划只是给决策变量多加了一个要求是整数的这个约束，因此两者的标准式之间基本没有差别</p>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/img/image-20220102173128816.png" alt="标准形式之间的关系"></p>
<h2 id="5-适合整数规划求解的问题"><a href="#5-适合整数规划求解的问题" class="headerlink" title="5. 适合整数规划求解的问题"></a>5. 适合整数规划求解的问题</h2><h3 id="A-合理下料问题"><a href="#A-合理下料问题" class="headerlink" title="A. 合理下料问题"></a>A. 合理下料问题</h3><blockquote>
<p>设用某型号的圆钢可以用于生产零件$A_1$， $A_2$，……，$A_m$ 。在一根圆钢上下料（切割）的方式有$B_1$，$B_2$，……，$B_n$ 种，每种下料方式可以得到各种零件的毛坯数以及用于生产的每种零件的需要量，如下表所示。问怎样安排下料方式，使得在满足生产需要的同时所用的圆钢数量最少？</p>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/img/image-20220102164618099.png" alt="每种下料方式可产生各种零件毛坯数量以及所需各类零件毛坯数量表" style="zoom:50%;"></p>
</blockquote>
<p>上面这个问题，需要的零件作为受限的资源，需要收益（消耗的圆钢）最少因此是一个数学规划问题</p>
<p>设$x_j$表示用$B_j$种下料方式生产的圆钢，则此时问题的数学模型为：</p>
<script type="math/tex; mode=display">
\min_{x_1,\cdots,x_n}z = \sum_{j=1}^n x_j\\
\begin {cases}
\sum_{j=1}^n {a_{ij}x_j} \ge b_i &i=1,\cdots,n\\
x_j \ge 0, &i=1,\cdots,n\\
x_j为整数
\end {cases}</script><h3 id="B-建厂问题"><a href="#B-建厂问题" class="headerlink" title="B. 建厂问题"></a>B. 建厂问题</h3><blockquote>
<p>某公司计划在m个地点建厂，可供选择的地点有$A<em>1$，$A_2$，……，$A_m$ ，在这些地点建立的工厂的生产能力分别是$a_1$， $a_2$，……，$a_m$（假设生产同一产品）。第 $i$个工厂的建设费用为$f_i,\ i=1,2,\cdots,m$。又有 $n$ 个地点$B_1$，$B_2$，……，$B_n$ 需要销售这 种产品，其销量分别为$b_1$，$b_2$，……，$b_n$ 。从工厂运往销地的单位运费为$c</em>{ij}$。试决定应在哪些地方建厂，既可以满足各地需要，又使总建设费用和总运输费用最少？</p>
</blockquote>
<p>同样，销量是限制的资源，而总费用作为收益需要最优，因此是一个规划问题</p>
<p>根据题意，可以列出下表</p>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/img/image-20220102170039401.png" alt="需求-产能-销量-建设费用表" style="zoom:50%;"></p>
<p>设$x_{ij}$为从工厂$i$运往销地$j$的运输量（$i=1,\cdots,m;j=1,\cdots n$），另设</p>
<script type="math/tex; mode=display">
Y_{ij}=
\begin{cases}
1, &在A_i处建厂\\
0, &不在A_i处建厂
\end{cases}</script><p>则建厂问题数学模型为:</p>
<script type="math/tex; mode=display">
\min_{x_{ij},y_i} Z=\sum_{j=1}^m\sum_{i=1}^nc_{ij}x_{ij}+\sum_{i=1}^mf_iy_i\\
\begin {cases}
\sum_{j=1}^n x_{ij} \leq a_iy_i,&i=1,\cdots,m\\
\sum_{i=1}^m x_{ij} \ge b_j, &j=1,\cdots,n\\
x_{ij}\ge 0, &i=1,\cdots,m;j=1,\cdots,n\\
y_i=1或y_i=0, &i=1,\cdots,m
\end{cases}</script><h2 id="6-整数规划的求解"><a href="#6-整数规划的求解" class="headerlink" title="6. 整数规划的求解"></a>6. 整数规划的求解</h2><p>从数学模型上看整数规划似乎是线性规划的 一种特殊形式，求解只需在线性规划的基础上， 通过四舍五入取整，寻求满足整数要求的解即可。 但实际上两者却有很大的不同，通过四舍五入有得到的整数解也不一定就是最优解，有时甚至不能保证所得到的解是整数可行解。</p>
<p>因此，针对整数规划就有了其他的求解算法。目前，对于求解整数规划常用的方法有：<strong>分支定界法</strong>和<strong>割平面法</strong>；对于0-1规划问题，常用的算法有<strong>隐枚举法</strong>和<strong>匈牙利算法</strong></p>
<h3 id="A-分支定界算法"><a href="#A-分支定界算法" class="headerlink" title="A. 分支定界算法"></a>A. 分支定界算法</h3><p><strong>分支定界算法的基本就是当作为松弛问题的线性规划问题的解为整数解的时候，整数规划的最优解就是松弛问题的最优解</strong></p>
<p>因此，分支定界算法的基本思想就是不断地对可行域进行划分（每次划分可行域实际上是添加新的约束），然后对所有的子可行域进行线性规划直到找到解为整数的解，此时该解可能为整数规划的一个最优解。</p>
<p>算法的自然语言描述如下：</p>
<ul>
<li><p>首先不考虑整数限制先求出相应松弛问题的最优解$\vec x=[x^0_1, \cdots, x^0_n]$</p>
<ul>
<li><p>若松弛问题无可行解，则ILP无可行解</p>
</li>
<li><p>若求得的松弛问题最优解符合整数要求，则是ILP的最优解</p>
</li>
<li><p>若不满足整数条件，则从最优解中选择一个不满足整数条件的变量，对其构造新的约束添加到松弛问题中形成两个子问题<br>添加的新的约束为</p>
<script type="math/tex; mode=display">
x_i\leq \lfloor x^0_i\rfloor或者x_i \ge \lceil x^0_i\rceil</script></li>
<li><p>依次在缩小的可行域中求解新构造的线性规划的最优解</p>
</li>
</ul>
</li>
<li><p>重复上述过程，直到子问题无解或有整数最优解（被查清）</p>
</li>
</ul>
<p>算法流程图如下：</p>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/img/image-20220102180932802.png" alt="分支定界算法流程图"></p>
<p>下面结合两个个例子来讲解分支定界算法</p>
<blockquote>
<p>求下面的整数规划问题</p>
<script type="math/tex; mode=display">
\max_{x_1, x_2} z=3x_1+2x_2\\
\begin {cases}
2x_1+3x_2 \leq 4\\
2x_1+x_2 \leq 24\\
x_1, x_2 \ge 0\\
x_1, x_2为整数
\end{cases}</script></blockquote>
<p>求解步骤如下：</p>
<ol>
<li><p><strong>求解松弛问题的解</strong></p>
<script type="math/tex; mode=display">
\max_{x_1, x_2} z=3x_1+2x_2\\
\begin {cases}
2x_1+3x_2 \leq 4\\
2x_1+x_2 \leq 24\\
x_1, x_2 \ge 0\\
\end{cases}</script><p>得</p>
<script type="math/tex; mode=display">
\begin {cases}
x_1=3.25\\
x_2=2.5\\
z_{max}=14.75\\
\end{cases}</script><p>此时松弛问题有解，但是决策变量$x_1$，$x_2$都不是整数，因此对两个变量每个都要添加新的约束</p>
</li>
<li><p><strong>首先对决策变量$x_1$添加约束</strong></p>
<script type="math/tex; mode=display">
\max_{x_1, x_2} z=3x_1+2x_2\\
\begin {cases}
2x_1+3x_2 \leq 4\\
2x_1+x_2 \leq 24\\
x_1\le 3\\
x_1, x_2 \ge 0\\
\end{cases}</script><p>求解，得</p>
<script type="math/tex; mode=display">
\begin {cases}
x_1=3\\
x_2=2.67\\
z_{max}=14.33\\
\end{cases}</script><p>添加另外一种约束</p>
<script type="math/tex; mode=display">
\max_{x_1, x_2} z=3x_1+2x_2\\
\begin {cases}
2x_1+3x_2 \leq 4\\
2x_1+x_2 \leq 24\\
x_1\ge 4\\
x_1, x_2 \ge 0\\
\end{cases}</script><p>求解得到第一个可能的解</p>
<script type="math/tex; mode=display">
\begin {cases}
x_1=4\\
x_2=1\\
z_{max}=14\\
\end{cases}</script></li>
<li><p><strong>接下来对决策变量$x_2$添加约束</strong></p>
<script type="math/tex; mode=display">
\max_{x_1, x_2} z=3x_1+2x_2\\
\begin {cases}
2x_1+3x_2 \leq 4\\
2x_1+x_2 \leq 24\\
x_1\le 3\\
x_2\leq 2\\
x_1, x_2 \ge 0\\
\end{cases}</script><p>得到一个可能的解</p>
<script type="math/tex; mode=display">
\begin {cases}
x_1=3\\
x_2=2\\
z_{max}=13\\
\end{cases}</script><p>然后添加另外一种约束</p>
<script type="math/tex; mode=display">
\max_{x_1, x_2} z=3x_1+2x_2\\
\begin {cases}
2x_1+3x_2 \leq 4\\
2x_1+x_2 \leq 24\\
x_1\le 3\\
x_2\ge 3\\
x_1, x_2 \ge 0\\
\end{cases}</script><p>得到解</p>
<script type="math/tex; mode=display">
\begin {cases}
x_1=2.2\\
x_2=3\\
z_{max}=13.5\\
\end{cases}</script></li>
<li><p>接下来重复步骤，直到所有的子问题的子问题的解都是整数解或者无解</p>
</li>
</ol>
<p>最终通过对所有的可能的解进行比较，得到最终的解为</p>
<script type="math/tex; mode=display">
\begin {cases}
x_1=4\\
x_2=1\\
z_{max}=14\\
\end{cases}</script><p>再举一个例子</p>
<blockquote>
<p>求下面的整数规划的解</p>
<script type="math/tex; mode=display">
\max_{x_1, x_2} z=x_1+x_2\\
\begin {cases}
x_1+\frac9{14}x_2 \leq \frac{51}{14}\\
-2x_1+x_2 \leq \frac 1 3\\
x_1, x_2 \ge 0\\
x_1, x_2为整数
\end{cases}</script></blockquote>
<p>同样，类似于上面的不断添加约束，最后得到一个搜索树，注意下面这个是深度优先的搜索树</p>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/img/image-20220102193325813.png" alt="问题二的搜索树"></p>
<h3 id="B-割平面算法"><a href="#B-割平面算法" class="headerlink" title="B. 割平面算法"></a>B. 割平面算法</h3><p>割平面算法的核心思想就是：</p>
<ol>
<li>对线性规划问题P添加约束等价于进一步缩小可行域（割去可行域）</li>
<li>对松弛问题P不断添加约束条件，即可行域不断地割去一块，使得非整数解恰好在割去的区域中而没有割去原问题的可行解，得到新问题P’</li>
<li>对问题P’继续进行线性规划，直到<ol>
<li>松弛问题无解，则整数规划问题无解</li>
<li>松弛问题最优解为整数向量，则整数规划的解就是松弛问题的解</li>
</ol>
</li>
</ol>
<p>下面结合一个例子讲解割平面算法</p>
<blockquote>
<p>求下面的整数规划</p>
<script type="math/tex; mode=display">
\max_{x_1,x_2}z=x_1+x_2\\
\begin{cases}
-x_1+x_2\leq 1\\
3x_1 +x_2 \leq4\\
x_1, x_2 \ge 0\\
x_1, x_2均为整数
\end{cases}</script></blockquote>
<p>上面这个例子的可行域如下，松弛问题的最优解为$(\frac 43,\frac34)$，因此对其进行分割。</p>
<p>割平面算法要求分割的时候分割的区域不能包含整数解，因此选择分割的两个区域为上边和右边的两个蓝色三角形。</p>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/img/image-20220102222730181.png" alt="上述例子的可行域"></p>
<p>对这两个区域进行分割后（添加约束后），新的问题P’为</p>
<script type="math/tex; mode=display">
\max_{x_1,x_2}z=x_1+x_2\\
\begin{cases}
-x_1+x_2\leq 1\\
3x_1 +x_2 \leq4\\
x_1, x_2 \ge 0\\
x_1\leq 1\\
x_2\leq 1\\
x_1, x_2均为整数
\end{cases}</script><p>此时对P’的松弛问题进行求解，得到解为</p>
<script type="math/tex; mode=display">
\begin {cases}
x_1=1\\
x_2=1\\
z_{max}=2\\
\end{cases}</script><p>此时松弛问题的解为整数解，因此算法结束。 </p>
<p>因此，割平面算法最关键的步骤就是在于判断该怎样对平面进行切割。具体来说进行切割的方法为引入松弛变量和剩余变量。这里就不再展开了。</p>
<h2 id="7-整数规划的Python求解"><a href="#7-整数规划的Python求解" class="headerlink" title="7. 整数规划的Python求解"></a>7. 整数规划的Python求解</h2><p>虽然我们上面介绍了如何在线性规划的基础上对整数规划问题进行求解的算法。但其实我们并不需要自己动手实现他们。正如我们前面所说的，数学建模的目的在于运用这个算法去解决实际问题而非去动手显示这些算法。</p>
<p>对整数规划问题进行求解，我们当然可以在前面介绍的SciPy的linprog的基础上自己动手实现这些算法，然而其实有其他的库已经帮助我们进行了这一步了，因此我们直接调用即可。</p>
<p>具体来说，这个库就是<code>PuLP</code>库，这是他的<a target="_blank" rel="noopener" href="https://coin-or.github.io/pulp/index.html">官网</a>：<a target="_blank" rel="noopener" href="https://coin-or.github.io/pulp/index.html">https://coin-or.github.io/pulp/index.html</a></p>
<p>从原理上来说，PuLP这个库是基于其他的线性规划求解程序，在PuLP这个库来说，这些求解线性规划的程序称为求解器。求解器提供了命令行的接口和API，因此PuLP其实就是对这些API做了一层Python Binding，从而实现的在Python中求解整数规划问题。</p>
<p>PuLP中默认的求解器是开源的CBC求解器，此外还支持很多其他的开源或者商业的求解器。不过CBC用来解决我们一般的几百个决策变量的规划问题肯定是足够了。</p>
<p>下面针对下面这个线性规划问题使用PuLP进行求解</p>
<script type="math/tex; mode=display">
\max_{x_1, x_2} z=x_1+x_2\\
\begin {cases}
x_1+\frac9{14}x_2 \leq \frac{51}{14}\\
-2x_1+x_2 \leq \frac 1 3\\
x_1, x_2 \ge 0\\
x_1, x_2为整数
\end{cases}</script><h3 id="A-定义问题"><a href="#A-定义问题" class="headerlink" title="A. 定义问题"></a>A. 定义问题</h3><p>PuLP求解线性规划问题第一步就是创建一个线性规划问题（Linear Program Problem，LpProblem）。PuLP中将线性规划问题抽象为一个类，而诸如约束条件、优化目标、决策变量等等都是该类下的属性</p>
<pre class="line-numbers language-python"><code class="language-python"><span class="token keyword">import</span> pulp

problem<span class="token punctuation">:</span> pulp<span class="token punctuation">.</span>LpProblem <span class="token operator">=</span> pulp<span class="token punctuation">.</span>LpProblem<span class="token punctuation">(</span>name<span class="token operator">=</span><span class="token string">"线性规划例子"</span><span class="token punctuation">,</span> sense<span class="token operator">=</span>pulp<span class="token punctuation">.</span>LpMaximize<span class="token punctuation">)</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span></span></code></pre>
<p>我们在初始化该类的时候需要指定该问题的名称，以及优化的类型，是最大值还是最小值</p>
<h3 id="B-创建决策变量"><a href="#B-创建决策变量" class="headerlink" title="B. 创建决策变量"></a>B. 创建决策变量</h3><p>同样，决策变量也被抽象为了一个类，因此我们需要对其进行初始化</p>
<pre class="line-numbers language-python"><code class="language-python">x1 <span class="token operator">=</span> pulp<span class="token punctuation">.</span>LpVariable<span class="token punctuation">(</span>name<span class="token operator">=</span><span class="token string">"x1"</span><span class="token punctuation">,</span> cat<span class="token operator">=</span>pulp<span class="token punctuation">.</span>LpInteger<span class="token punctuation">,</span> lowBound<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">)</span>
x2 <span class="token operator">=</span> pulp<span class="token punctuation">.</span>LpVariable<span class="token punctuation">(</span>name<span class="token operator">=</span><span class="token string">"x2"</span><span class="token punctuation">,</span> cat<span class="token operator">=</span>pulp<span class="token punctuation">.</span>LpInteger<span class="token punctuation">,</span> lowBound<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">)</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span></span></code></pre>
<p>我们在创建决策变量的时候首先需要指定决策变量的名称，然后指定其类型，因为我们要求解的整数规划问题，因此我们指定这两个变量的取值是整数。</p>
<p>此外我们还指定了这两个变量的下界都是0，类似与SciPy中连续的线性规划，我们不指定上界（上届为None）的时候，默认是无穷</p>
<h3 id="C-设置优化目标和约束"><a href="#C-设置优化目标和约束" class="headerlink" title="C. 设置优化目标和约束"></a>C. 设置优化目标和约束</h3><p>我们设置优化目标和添加约束的时候，既可以通过LpProblem类的接口显示的添加，也可以通过其重载的运算符完成</p>
<pre class="line-numbers language-python"><code class="language-python">problem<span class="token punctuation">.</span>setObjective<span class="token punctuation">(</span>x1 <span class="token operator">+</span> x2<span class="token punctuation">)</span>

problem <span class="token operator">+=</span> x1 <span class="token operator">+</span> <span class="token number">9</span><span class="token operator">/</span><span class="token number">14</span> <span class="token operator">*</span> x2 <span class="token operator">&lt;=</span><span class="token number">51</span><span class="token operator">/</span><span class="token number">14</span><span class="token punctuation">,</span> <span class="token string">"约束1"</span>
problem <span class="token operator">+=</span> pulp<span class="token punctuation">.</span>LpConstraint<span class="token punctuation">(</span>e<span class="token operator">=</span><span class="token punctuation">(</span><span class="token operator">-</span><span class="token number">2</span> <span class="token operator">*</span> x1 <span class="token operator">+</span> x2<span class="token punctuation">)</span><span class="token punctuation">,</span> sense<span class="token operator">=</span>pulp<span class="token punctuation">.</span>LpConstraintLE<span class="token punctuation">,</span> rhs<span class="token operator">=</span><span class="token number">1</span><span class="token operator">/</span><span class="token number">3</span><span class="token punctuation">,</span> name<span class="token operator">=</span><span class="token string">"约束2"</span><span class="token punctuation">)</span>
<span class="token comment" spellcheck="true"># problem += -2 * x1 + x2 &lt;= 1/3, "约束2"</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>上面我们设定优化目标是$x_1+x_2$，然后分别通过problem重载的+=符号、提供的类进行约束添加</p>
<p>我们此时可以打印一下problem，就能够看到添加了目标和约束之后的问题</p>
<pre class="line-numbers language-python"><code class="language-python"><span class="token operator">>></span><span class="token operator">></span> <span class="token keyword">print</span><span class="token punctuation">(</span>problem<span class="token punctuation">)</span>
线性规划例子<span class="token punctuation">:</span>
MAXIMIZE
<span class="token number">1</span><span class="token operator">*</span>x1 <span class="token operator">+</span> <span class="token number">1</span><span class="token operator">*</span>x2 <span class="token operator">+</span> <span class="token number">0</span>
SUBJECT TO
约束<span class="token number">1</span><span class="token punctuation">:</span> x1 <span class="token operator">+</span> <span class="token number">0.642857142857</span> x2 <span class="token operator">&lt;=</span> <span class="token number">3.64285714286</span>

约束<span class="token number">2</span><span class="token punctuation">:</span> <span class="token operator">-</span> <span class="token number">2</span> x1 <span class="token operator">+</span> x2 <span class="token operator">&lt;=</span> <span class="token number">0.333333333333</span>

VARIABLES
<span class="token number">0</span> <span class="token operator">&lt;=</span> x1 Integer
<span class="token number">0</span> <span class="token operator">&lt;=</span> x2 Integer
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/img/image-20220103151645040.png" alt="运行结果"></p>
<h3 id="D-求解"><a href="#D-求解" class="headerlink" title="D. 求解"></a>D. 求解</h3><p>由于并不是所有的问题都是可解的因此在对问题进行求解后，实际上问题会有很多种状态，所有的解的状态保存在pulp.LpStatus这个常量中</p>
<pre class="line-numbers language-python"><code class="language-python"><span class="token operator">>></span><span class="token operator">></span> <span class="token keyword">import</span> pprint
<span class="token operator">>></span><span class="token operator">></span> pprint<span class="token punctuation">.</span><span class="token keyword">print</span><span class="token punctuation">(</span>pulp<span class="token punctuation">.</span>LpStatus<span class="token punctuation">)</span>
<span class="token punctuation">{</span><span class="token operator">-</span><span class="token number">3</span><span class="token punctuation">:</span> <span class="token string">'Undefined'</span><span class="token punctuation">,</span>
 <span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">:</span> <span class="token string">'Unbounded'</span><span class="token punctuation">,</span>
 <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">:</span> <span class="token string">'Infeasible'</span><span class="token punctuation">,</span>
 <span class="token number">0</span><span class="token punctuation">:</span> <span class="token string">'Not Solved'</span><span class="token punctuation">,</span>
 <span class="token number">1</span><span class="token punctuation">:</span> <span class="token string">'Optimal'</span><span class="token punctuation">}</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>其中，</p>
<ul>
<li>Optimal表示已经得到了最优解</li>
<li>Not Sloved，即problem在求解前的状态</li>
<li>Infeasible，即问题不存在可行解，例如我们的约束中出现了$2\leq x \leq -1$这样的条件</li>
<li>Unbounded，即得到的答案是无穷，例如优化目标为$z=3x$，而约束为$1\leq x$</li>
<li>Undefined，即问题可能存在最优解，但是求解器的求解算法没有得出解</li>
</ul>
<p>因此，在我们对问题求解之后，只有Optimal才会得到最终的答案，所以我们求解结束之后输出的时候需要检查一下状态</p>
<pre class="line-numbers language-python"><code class="language-python"><span class="token keyword">print</span><span class="token punctuation">(</span>problem<span class="token punctuation">)</span>

<span class="token keyword">if</span> pulp<span class="token punctuation">.</span>LpStatus<span class="token punctuation">[</span>status<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token string">"Optimal"</span><span class="token punctuation">:</span>
    variable<span class="token punctuation">:</span> pulp<span class="token punctuation">.</span>LpVariable
    <span class="token keyword">for</span> variable <span class="token keyword">in</span> problem<span class="token punctuation">.</span>variables<span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">:</span>
        <span class="token keyword">print</span><span class="token punctuation">(</span>f<span class="token string">"{variable.name}={variable.varValue}"</span><span class="token punctuation">)</span>
    <span class="token keyword">print</span><span class="token punctuation">(</span>pulp<span class="token punctuation">.</span>value<span class="token punctuation">(</span>problem<span class="token punctuation">.</span>objective<span class="token punctuation">)</span><span class="token punctuation">)</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h3 id="E-完整代码"><a href="#E-完整代码" class="headerlink" title="E. 完整代码"></a>E. 完整代码</h3><p>完整代码如下</p>
<pre class="line-numbers language-python"><code class="language-python"><span class="token keyword">import</span> pulp

problem<span class="token punctuation">:</span> pulp<span class="token punctuation">.</span>LpProblem <span class="token operator">=</span> pulp<span class="token punctuation">.</span>LpProblem<span class="token punctuation">(</span>name<span class="token operator">=</span><span class="token string">"线性规划例子"</span><span class="token punctuation">,</span> sense<span class="token operator">=</span>pulp<span class="token punctuation">.</span>LpMaximize<span class="token punctuation">)</span>

x1 <span class="token operator">=</span> pulp<span class="token punctuation">.</span>LpVariable<span class="token punctuation">(</span>name<span class="token operator">=</span><span class="token string">"x1"</span><span class="token punctuation">,</span> cat<span class="token operator">=</span>pulp<span class="token punctuation">.</span>LpInteger<span class="token punctuation">,</span> lowBound<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">)</span>
x2 <span class="token operator">=</span> pulp<span class="token punctuation">.</span>LpVariable<span class="token punctuation">(</span>name<span class="token operator">=</span><span class="token string">"x2"</span><span class="token punctuation">,</span> cat<span class="token operator">=</span>pulp<span class="token punctuation">.</span>LpInteger<span class="token punctuation">,</span> lowBound<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">)</span>

problem<span class="token punctuation">.</span>setObjective<span class="token punctuation">(</span>x1 <span class="token operator">+</span> x2<span class="token punctuation">)</span>

problem <span class="token operator">+=</span> x1 <span class="token operator">+</span> <span class="token number">9</span><span class="token operator">/</span><span class="token number">14</span> <span class="token operator">*</span> x2 <span class="token operator">&lt;=</span><span class="token number">51</span><span class="token operator">/</span><span class="token number">14</span><span class="token punctuation">,</span> <span class="token string">"约束1"</span>
problem <span class="token operator">+=</span> pulp<span class="token punctuation">.</span>LpConstraint<span class="token punctuation">(</span>e<span class="token operator">=</span><span class="token punctuation">(</span><span class="token operator">-</span><span class="token number">2</span> <span class="token operator">*</span> x1 <span class="token operator">+</span> x2<span class="token punctuation">)</span><span class="token punctuation">,</span> sense<span class="token operator">=</span>pulp<span class="token punctuation">.</span>LpConstraintLE<span class="token punctuation">,</span> rhs<span class="token operator">=</span><span class="token number">1</span><span class="token operator">/</span><span class="token number">3</span><span class="token punctuation">,</span> name<span class="token operator">=</span><span class="token string">"约束2"</span><span class="token punctuation">)</span>
<span class="token comment" spellcheck="true"># problem += -2 * x1 + x2 &lt;= 1/3, "约束2"</span>


status <span class="token operator">=</span> problem<span class="token punctuation">.</span>solve<span class="token punctuation">(</span><span class="token punctuation">)</span>

<span class="token comment" spellcheck="true"># print(status)</span>
<span class="token keyword">print</span><span class="token punctuation">(</span>problem<span class="token punctuation">)</span>

<span class="token keyword">if</span> pulp<span class="token punctuation">.</span>LpStatus<span class="token punctuation">[</span>status<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token string">"Optimal"</span><span class="token punctuation">:</span>
    variable<span class="token punctuation">:</span> pulp<span class="token punctuation">.</span>LpVariable
    <span class="token keyword">for</span> variable <span class="token keyword">in</span> problem<span class="token punctuation">.</span>variables<span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">:</span>
        <span class="token keyword">print</span><span class="token punctuation">(</span>f<span class="token string">"{variable.name}={variable.varValue}"</span><span class="token punctuation">)</span>
    <span class="token keyword">print</span><span class="token punctuation">(</span>pulp<span class="token punctuation">.</span>value<span class="token punctuation">(</span>problem<span class="token punctuation">.</span>objective<span class="token punctuation">)</span><span class="token punctuation">)</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>运行后的输出</p>
<pre class="line-numbers language-bash"><code class="language-bash">Welcome to the CBC MILP Solver 
Version: 2.10.3 
Build Date: Dec 15 2019 

<span class="token function">command</span> line - /home/jack/anaconda3/envs/mm/lib/python3.9/site-packages/pulp/apis/<span class="token punctuation">..</span>/solverdir/cbc/linux/64/cbc /tmp/5cf19a184e774fe995d025bd3de8e4c9-pulp.mps max timeMode elapsed branch printingOptions all solution /tmp/5cf19a184e774fe995d025bd3de8e4c9-pulp.sol <span class="token punctuation">(</span>default strategy 1<span class="token punctuation">)</span>
At line 2 NAME          MODEL
At line 3 ROWS
At line 7 COLUMNS
At line 18 RHS
At line 21 BOUNDS
At line 24 ENDATA
Problem MODEL has 2 rows, 2 columns and 4 elements
Coin0008I MODEL <span class="token function">read</span> with 0 errors
Option <span class="token keyword">for</span> timeMode changed from cpu to elapsed
Continuous objective value is 4.83333 - 0.00 seconds
Cgl0003I 0 fixed, 1 tightened bounds, 0 strengthened rows, 0 substitutions
Cgl0004I processed model has 2 rows, 2 columns <span class="token punctuation">(</span>2 integer <span class="token punctuation">(</span>0 of <span class="token function">which</span> binary<span class="token punctuation">))</span> and 4 elements
Cutoff increment increased from 1e-05 to 0.9999
Cbc0012I Integer solution of -4 found by DiveCoefficient after 0 iterations and 0 nodes <span class="token punctuation">(</span>0.00 seconds<span class="token punctuation">)</span>
Cbc0001I Search completed - best objective -4, took 0 iterations and 0 nodes <span class="token punctuation">(</span>0.00 seconds<span class="token punctuation">)</span>
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
Cuts at root node changed objective from -4.83333 to -4.83333
Probing was tried 0 <span class="token function">times</span> and created 0 cuts of <span class="token function">which</span> 0 were active after adding rounds of cuts <span class="token punctuation">(</span>0.000 seconds<span class="token punctuation">)</span>
Gomory was tried 0 <span class="token function">times</span> and created 0 cuts of <span class="token function">which</span> 0 were active after adding rounds of cuts <span class="token punctuation">(</span>0.000 seconds<span class="token punctuation">)</span>
Knapsack was tried 0 <span class="token function">times</span> and created 0 cuts of <span class="token function">which</span> 0 were active after adding rounds of cuts <span class="token punctuation">(</span>0.000 seconds<span class="token punctuation">)</span>
Clique was tried 0 <span class="token function">times</span> and created 0 cuts of <span class="token function">which</span> 0 were active after adding rounds of cuts <span class="token punctuation">(</span>0.000 seconds<span class="token punctuation">)</span>
MixedIntegerRounding2 was tried 0 <span class="token function">times</span> and created 0 cuts of <span class="token function">which</span> 0 were active after adding rounds of cuts <span class="token punctuation">(</span>0.000 seconds<span class="token punctuation">)</span>
FlowCover was tried 0 <span class="token function">times</span> and created 0 cuts of <span class="token function">which</span> 0 were active after adding rounds of cuts <span class="token punctuation">(</span>0.000 seconds<span class="token punctuation">)</span>
TwoMirCuts was tried 0 <span class="token function">times</span> and created 0 cuts of <span class="token function">which</span> 0 were active after adding rounds of cuts <span class="token punctuation">(</span>0.000 seconds<span class="token punctuation">)</span>
ZeroHalf was tried 0 <span class="token function">times</span> and created 0 cuts of <span class="token function">which</span> 0 were active after adding rounds of cuts <span class="token punctuation">(</span>0.000 seconds<span class="token punctuation">)</span>

Result - Optimal solution found

Objective value:                4.00000000
Enumerated nodes:               0
Total iterations:               0
Time <span class="token punctuation">(</span>CPU seconds<span class="token punctuation">)</span>:             0.00
Time <span class="token punctuation">(</span>Wallclock seconds<span class="token punctuation">)</span>:       0.00

Option <span class="token keyword">for</span> printingOptions changed from normal to all
Total <span class="token function">time</span> <span class="token punctuation">(</span>CPU seconds<span class="token punctuation">)</span>:       0.00   <span class="token punctuation">(</span>Wallclock seconds<span class="token punctuation">)</span>:       0.00

线性规划例子:
MAXIMIZE
1*x1 + 1*x2 + 0
SUBJECT TO
约束1: x1 + 0.642857142857 x2 <span class="token operator">&lt;=</span> 3.64285714286

约束2: - 2 x1 + x2 <span class="token operator">&lt;=</span> 0.333333333333

VARIABLES
0 <span class="token operator">&lt;=</span> x1 Integer
0 <span class="token operator">&lt;=</span> x2 Integer

x1<span class="token operator">=</span>2.0
x2<span class="token operator">=</span>2.0
4.0
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/img/image-20220103153434192.png" alt="求解后的输出"></p>
<h2 id="8-整数规划的例子"><a href="#8-整数规划的例子" class="headerlink" title="8. 整数规划的例子"></a>8. 整数规划的例子</h2><p>最后举一个真实的整数规划的数学建模的例子结束这一章</p>
<h3 id="A-最优生产问题"><a href="#A-最优生产问题" class="headerlink" title="A. 最优生产问题"></a>A. 最优生产问题</h3><blockquote>
<p>已知AM工厂是一个拥有四个车间的玩具生产厂商，该厂商今年新设计出A、B、C、D、E、F六种玩具模型，根据以前的生产情况及市场调查预测，得知生产每单位产品所需的工时、每个车间在一季度的工时上限以及产品的预测价格，如下表所示。问∶每种设计产品在这个季度各应生产多少，才能使AM工厂这个季度的生产总值达到最大?</p>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/img/image-20220103154101580.png" alt="工时上限以及价格表" style="zoom:67%;"></p>
</blockquote>
<h3 id="B-基本假设"><a href="#B-基本假设" class="headerlink" title="B. 基本假设"></a>B. 基本假设</h3><ul>
<li>利润越高越好</li>
<li>各个种类玩具都为整数</li>
</ul>
<h3 id="C-符号假设"><a href="#C-符号假设" class="headerlink" title="C. 符号假设"></a>C. 符号假设</h3><ul>
<li>设各种玩具生产数量为$x_i, i=1,\cdots,6$，则$x_i$为整数</li>
<li>设利润为$Z$，则$Z=20x_1+14x_2+16x_3+36x_4+32x_5+30x_6$</li>
</ul>
<h3 id="D-模型建立"><a href="#D-模型建立" class="headerlink" title="D. 模型建立"></a>D. 模型建立</h3><p>根据题意，得到下面的整数规划模型</p>
<script type="math/tex; mode=display">
\max_{\vec x} z=[20,14,16,36,32,30]\vec x^T\\
\begin {cases}
[0.01, 0.01,0.01,0.03,0.03,0.03]\vec x^T\leq 850\\
[0.02, 0, 0, 0.05, 0, 0]\vec x^T\leq700\\
[0, 0.02,0,0,0.05,0]\vec x^T\leq100\\
[0,0,0.03,0,0,0.08]\vec x^T\leq900\\
x_i \ge 0,&i=1,\cdots,6
\end {cases}</script><h3 id="E-编程求解"><a href="#E-编程求解" class="headerlink" title="E. 编程求解"></a>E. 编程求解</h3><p>代码如下</p>
<pre class="line-numbers language-python"><code class="language-python"><span class="token keyword">import</span> pulp
<span class="token keyword">import</span> numpy <span class="token keyword">as</span> np

problem<span class="token punctuation">:</span> pulp<span class="token punctuation">.</span>LpProblem <span class="token operator">=</span> pulp<span class="token punctuation">.</span>LpProblem<span class="token punctuation">(</span>name<span class="token operator">=</span><span class="token string">"玩具最优生产问题"</span><span class="token punctuation">,</span> sense<span class="token operator">=</span>pulp<span class="token punctuation">.</span>LpMaximize<span class="token punctuation">)</span>

variables <span class="token operator">=</span> np<span class="token punctuation">.</span>array<span class="token punctuation">(</span><span class="token punctuation">[</span>pulp<span class="token punctuation">.</span>LpVariable<span class="token punctuation">(</span>name<span class="token operator">=</span>f<span class="token string">"x_{i}"</span><span class="token punctuation">,</span> cat<span class="token operator">=</span>pulp<span class="token punctuation">.</span>LpInteger<span class="token punctuation">,</span> lowBound<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">)</span> <span class="token keyword">for</span> i <span class="token keyword">in</span> range<span class="token punctuation">(</span><span class="token number">6</span><span class="token punctuation">)</span><span class="token punctuation">]</span><span class="token punctuation">,</span> dtype<span class="token operator">=</span>object<span class="token punctuation">)</span>

jia <span class="token operator">=</span> np<span class="token punctuation">.</span>array<span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">0.01</span><span class="token punctuation">,</span> <span class="token number">0.01</span><span class="token punctuation">,</span><span class="token number">0.01</span><span class="token punctuation">,</span><span class="token number">0.03</span><span class="token punctuation">,</span><span class="token number">0.03</span><span class="token punctuation">,</span><span class="token number">0.03</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
yi <span class="token operator">=</span> np<span class="token punctuation">.</span>array<span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">0.02</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">0.05</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
bing <span class="token operator">=</span> np<span class="token punctuation">.</span>array<span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">0.02</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">0.05</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
ding <span class="token operator">=</span> np<span class="token punctuation">.</span>array<span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">0.03</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">0.08</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
profits <span class="token operator">=</span> np<span class="token punctuation">.</span>array<span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">20</span><span class="token punctuation">,</span><span class="token number">14</span><span class="token punctuation">,</span><span class="token number">16</span><span class="token punctuation">,</span><span class="token number">36</span><span class="token punctuation">,</span><span class="token number">32</span><span class="token punctuation">,</span><span class="token number">30</span><span class="token punctuation">]</span><span class="token punctuation">)</span>

problem <span class="token operator">+=</span> jia @ variables <span class="token operator">&lt;=</span> <span class="token number">850</span><span class="token punctuation">,</span> <span class="token string">"甲工厂工时约束"</span>
problem <span class="token operator">+=</span> yi @ variables <span class="token operator">&lt;=</span> <span class="token number">700</span><span class="token punctuation">,</span> <span class="token string">"乙工厂工时约束"</span>
problem <span class="token operator">+=</span> bing @ variables <span class="token operator">&lt;=</span> <span class="token number">100</span><span class="token punctuation">,</span> <span class="token string">"丙工厂工时约束"</span>
problem <span class="token operator">+=</span> ding @ variables <span class="token operator">&lt;=</span> <span class="token number">900</span><span class="token punctuation">,</span> <span class="token string">"丁工厂工时约束"</span>

problem<span class="token punctuation">.</span>setObjective<span class="token punctuation">(</span>profits @ variables<span class="token punctuation">)</span>

<span class="token keyword">print</span><span class="token punctuation">(</span>problem<span class="token punctuation">)</span>

<span class="token keyword">if</span> pulp<span class="token punctuation">.</span>LpStatus<span class="token punctuation">[</span>problem<span class="token punctuation">.</span>solve<span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token string">"Optimal"</span><span class="token punctuation">:</span>
    variable<span class="token punctuation">:</span> pulp<span class="token punctuation">.</span>LpVariable
    <span class="token keyword">for</span> variable <span class="token keyword">in</span> problem<span class="token punctuation">.</span>variables<span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">:</span>
        <span class="token keyword">print</span><span class="token punctuation">(</span>f<span class="token string">"{variable.name} = {variable.varValue}"</span><span class="token punctuation">)</span>
    <span class="token keyword">print</span><span class="token punctuation">(</span>pulp<span class="token punctuation">.</span>value<span class="token punctuation">(</span>problem<span class="token punctuation">.</span>objective<span class="token punctuation">)</span><span class="token punctuation">)</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>输出</p>
<pre class="line-numbers language-python"><code class="language-python">玩具最优生产问题<span class="token punctuation">:</span>
MAXIMIZE
<span class="token number">20</span><span class="token operator">*</span>x_0 <span class="token operator">+</span> <span class="token number">14</span><span class="token operator">*</span>x_1 <span class="token operator">+</span> <span class="token number">16</span><span class="token operator">*</span>x_2 <span class="token operator">+</span> <span class="token number">36</span><span class="token operator">*</span>x_3 <span class="token operator">+</span> <span class="token number">32</span><span class="token operator">*</span>x_4 <span class="token operator">+</span> <span class="token number">30</span><span class="token operator">*</span>x_5 <span class="token operator">+</span> <span class="token number">0</span>
SUBJECT TO
甲工厂工时约束<span class="token punctuation">:</span> <span class="token number">0.01</span> x_0 <span class="token operator">+</span> <span class="token number">0.01</span> x_1 <span class="token operator">+</span> <span class="token number">0.01</span> x_2 <span class="token operator">+</span> <span class="token number">0.03</span> x_3 <span class="token operator">+</span> <span class="token number">0.03</span> x_4 <span class="token operator">+</span> <span class="token number">0.03</span> x_5
 <span class="token operator">&lt;=</span> <span class="token number">850</span>

乙工厂工时约束<span class="token punctuation">:</span> <span class="token number">0.02</span> x_0 <span class="token operator">+</span> <span class="token number">0.05</span> x_3 <span class="token operator">&lt;=</span> <span class="token number">700</span>

丙工厂工时约束<span class="token punctuation">:</span> <span class="token number">0.02</span> x_1 <span class="token operator">+</span> <span class="token number">0.05</span> x_4 <span class="token operator">&lt;=</span> <span class="token number">100</span>

丁工厂工时约束<span class="token punctuation">:</span> <span class="token number">0.03</span> x_2 <span class="token operator">+</span> <span class="token number">0.08</span> x_5 <span class="token operator">&lt;=</span> <span class="token number">900</span>

VARIABLES
<span class="token number">0</span> <span class="token operator">&lt;=</span> x_0 Integer
<span class="token number">0</span> <span class="token operator">&lt;=</span> x_1 Integer
<span class="token number">0</span> <span class="token operator">&lt;=</span> x_2 Integer
<span class="token number">0</span> <span class="token operator">&lt;=</span> x_3 Integer
<span class="token number">0</span> <span class="token operator">&lt;=</span> x_4 Integer
<span class="token number">0</span> <span class="token operator">&lt;=</span> x_5 Integer


Result <span class="token operator">-</span> Optimal solution found

Objective value<span class="token punctuation">:</span>                <span class="token number">1250000.00000000</span>
Enumerated nodes<span class="token punctuation">:</span>               <span class="token number">0</span>
Total iterations<span class="token punctuation">:</span>               <span class="token number">0</span>
Time <span class="token punctuation">(</span>CPU seconds<span class="token punctuation">)</span><span class="token punctuation">:</span>             <span class="token number">0.00</span>
Time <span class="token punctuation">(</span>Wallclock seconds<span class="token punctuation">)</span><span class="token punctuation">:</span>       <span class="token number">0.00</span>

Option <span class="token keyword">for</span> printingOptions changed <span class="token keyword">from</span> normal to all
Total time <span class="token punctuation">(</span>CPU seconds<span class="token punctuation">)</span><span class="token punctuation">:</span>       <span class="token number">0.00</span>   <span class="token punctuation">(</span>Wallclock seconds<span class="token punctuation">)</span><span class="token punctuation">:</span>       <span class="token number">0.00</span>

x_0 <span class="token operator">=</span> <span class="token number">35000.0</span>
x_1 <span class="token operator">=</span> <span class="token number">5000.0</span>
x_2 <span class="token operator">=</span> <span class="token number">30000.0</span>
x_3 <span class="token operator">=</span> <span class="token number">0.0</span>
x_4 <span class="token operator">=</span> <span class="token number">0.0</span>
x_5 <span class="token operator">=</span> <span class="token number">0.0</span>
<span class="token number">1250000.0</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

                
            </div>
            <hr/>

            

    <div class="reprint" id="reprint-statement">
        
            <div class="reprint__author">
                <span class="reprint-meta" style="font-weight: bold;">
                    <i class="fas fa-user">
                        文章作者:
                    </i>
                </span>
                <span class="reprint-info">
                    <a href="/about" rel="external nofollow noreferrer">Jack Wang</a>
                </span>
            </div>
            <div class="reprint__type">
                <span class="reprint-meta" style="font-weight: bold;">
                    <i class="fas fa-link">
                        文章链接:
                    </i>
                </span>
                <span class="reprint-info">
                    <a href="https://jackwang0107.github.io/2022/01/02/shu-xue-jian-mo-suan-fa-2-zheng-shu-gui-hua/">https://jackwang0107.github.io/2022/01/02/shu-xue-jian-mo-suan-fa-2-zheng-shu-gui-hua/</a>
                </span>
            </div>
            <div class="reprint__notice">
                <span class="reprint-meta" style="font-weight: bold;">
                    <i class="fas fa-copyright">
                        版权声明:
                    </i>
                </span>
                <span class="reprint-info">
                    本博客所有文章除特別声明外，均采用
                    <a href="https://creativecommons.org/licenses/by/4.0/deed.zh" rel="external nofollow noreferrer" target="_blank">CC BY 4.0</a>
                    许可协议。转载请注明来源
                    <a href="/about" target="_blank">Jack Wang</a>
                    !
                </span>
            </div>
        
    </div>

    <script async defer>
      document.addEventListener("copy", function (e) {
        let toastHTML = '<span>复制成功，请遵循本文的转载规则</span><button class="btn-flat toast-action" onclick="navToReprintStatement()" style="font-size: smaller">查看</a>';
        M.toast({html: toastHTML})
      });

      function navToReprintStatement() {
        $("html, body").animate({scrollTop: $("#reprint-statement").offset().top - 80}, 800);
      }
    </script>



            <div class="tag_share" style="display: block;">
                <div class="post-meta__tag-list" style="display: inline-block;">
                    
                        <div class="article-tag">
                            
                                <a href="/tags/Python/">
                                    <span class="chip bg-color">Python</span>
                                </a>
                            
                                <a href="/tags/Math-Modeling/">
                                    <span class="chip bg-color">Math Modeling</span>
                                </a>
                            
                                <a href="/tags/Linear-Programming/">
                                    <span class="chip bg-color">Linear Programming</span>
                                </a>
                            
                                <a href="/tags/%E6%95%B4%E6%95%B0%E8%A7%84%E5%88%92/">
                                    <span class="chip bg-color">整数规划</span>
                                </a>
                            
                        </div>
                    
                </div>
                <div class="post_share" style="zoom: 80%; width: fit-content; display: inline-block; float: right; margin: -0.15rem 0;">
                    <link rel="stylesheet" type="text/css" href="/libs/share/css/share.min.css">
<div id="article-share">

    
    <div class="social-share" data-sites="twitter,facebook,google,qq,qzone,wechat,weibo,douban,linkedin" data-wechat-qrcode-helper="<p>微信扫一扫即可分享！</p>"></div>
    <script src="/libs/share/js/social-share.min.js"></script>
    

    

</div>

                </div>
            </div>
            
                <style>
    #reward {
        margin: 40px 0;
        text-align: center;
    }

    #reward .reward-link {
        font-size: 1.4rem;
        line-height: 38px;
    }

    #reward .btn-floating:hover {
        box-shadow: 0 6px 12px rgba(0, 0, 0, 0.2), 0 5px 15px rgba(0, 0, 0, 0.2);
    }

    #rewardModal {
        width: 320px;
        height: 350px;
    }

    #rewardModal .reward-title {
        margin: 15px auto;
        padding-bottom: 5px;
    }

    #rewardModal .modal-content {
        padding: 10px;
    }

    #rewardModal .close {
        position: absolute;
        right: 15px;
        top: 15px;
        color: rgba(0, 0, 0, 0.5);
        font-size: 1.3rem;
        line-height: 20px;
        cursor: pointer;
    }

    #rewardModal .close:hover {
        color: #ef5350;
        transform: scale(1.3);
        -moz-transform:scale(1.3);
        -webkit-transform:scale(1.3);
        -o-transform:scale(1.3);
    }

    #rewardModal .reward-tabs {
        margin: 0 auto;
        width: 210px;
    }

    .reward-tabs .tabs {
        height: 38px;
        margin: 10px auto;
        padding-left: 0;
    }

    .reward-content ul {
        padding-left: 0 !important;
    }

    .reward-tabs .tabs .tab {
        height: 38px;
        line-height: 38px;
    }

    .reward-tabs .tab a {
        color: #fff;
        background-color: #ccc;
    }

    .reward-tabs .tab a:hover {
        background-color: #ccc;
        color: #fff;
    }

    .reward-tabs .wechat-tab .active {
        color: #fff !important;
        background-color: #22AB38 !important;
    }

    .reward-tabs .alipay-tab .active {
        color: #fff !important;
        background-color: #019FE8 !important;
    }

    .reward-tabs .reward-img {
        width: 210px;
        height: 210px;
    }
</style>

<div id="reward">
    <a href="#rewardModal" class="reward-link modal-trigger btn-floating btn-medium waves-effect waves-light red">赏</a>

    <!-- Modal Structure -->
    <div id="rewardModal" class="modal">
        <div class="modal-content">
            <a class="close modal-close"><i class="fas fa-times"></i></a>
            <h4 class="reward-title">你的赏识是我前进的动力</h4>
            <div class="reward-content">
                <div class="reward-tabs">
                    <ul class="tabs row">
                        <li class="tab col s6 alipay-tab waves-effect waves-light"><a href="#alipay">支付宝</a></li>
                        <li class="tab col s6 wechat-tab waves-effect waves-light"><a href="#wechat">微 信</a></li>
                    </ul>
                    <div id="alipay">
                        <img src="/medias/reward/alipay.png" class="reward-img" alt="支付宝打赏二维码">
                    </div>
                    <div id="wechat">
                        <img src="/medias/reward/wechat.jpg" class="reward-img" alt="微信打赏二维码">
                    </div>
                </div>
            </div>
        </div>
    </div>
</div>

<script>
    $(function () {
        $('.tabs').tabs();
    });
</script>

            
        </div>
    </div>

    

    

    

    

    

    

    

    

    

<article id="prenext-posts" class="prev-next articles">
    <div class="row article-row">
        
        <div class="article col s12 m6" data-aos="fade-up">
            <div class="article-badge left-badge text-color">
                <i class="fas fa-chevron-left"></i>&nbsp;上一篇</div>
            <div class="card">
                <a href="/2022/01/03/python-zhong-de-tui-dao-shi/">
                    <div class="card-image">
                        
                        <img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/img/20201221215820109.png" class="responsive-img" alt="Python中的推导式">
                        
                        <span class="card-title">Python中的推导式</span>
                    </div>
                </a>
                <div class="card-content article-content">
                    <div class="summary block-with-text">
                        
                            本文是我CSDN中的文章，完成于2019年，现将其迁移到我的个人博客网站。本文主要介绍了Python中的推导式
                        
                    </div>
                    <div class="publish-info">
                        <span class="publish-date">
                            <i class="far fa-clock fa-fw icon-date"></i>2022-01-03
                        </span>
                        <span class="publish-author">
                            
                            <i class="fas fa-user fa-fw"></i>
                            Jack Wang
                            
                        </span>
                    </div>
                </div>
                
                <div class="card-action article-tags">
                    
                    <a href="/tags/Python/">
                        <span class="chip bg-color">Python</span>
                    </a>
                    
                    <a href="/tags/%E6%9D%82%E9%A1%B9/">
                        <span class="chip bg-color">杂项</span>
                    </a>
                    
                    <a href="/tags/Python-Comprehension/">
                        <span class="chip bg-color">Python Comprehension</span>
                    </a>
                    
                    <a href="/tags/Python-%E6%8E%A8%E5%AF%BC%E5%BC%8F/">
                        <span class="chip bg-color">Python 推导式</span>
                    </a>
                    
                    <a href="/tags/CSDN-Blog-Transfer/">
                        <span class="chip bg-color">CSDN Blog Transfer</span>
                    </a>
                    
                </div>
                
            </div>
        </div>
        
        
        <div class="article col s12 m6" data-aos="fade-up">
            <div class="article-badge right-badge text-color">
                下一篇&nbsp;<i class="fas fa-chevron-right"></i>
            </div>
            <div class="card">
                <a href="/2022/01/01/shu-xue-jian-mo-suan-fa-1-xian-xing-gui-hua/">
                    <div class="card-image">
                        
                        <img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/img/359b033b5bb5c9eab88c9fcdd439b6003af3b3a5" class="responsive-img" alt="数学建模算法1-线性规划">
                        
                        <span class="card-title">数学建模算法1-线性规划</span>
                    </div>
                </a>
                <div class="card-content article-content">
                    <div class="summary block-with-text">
                        
                            本文主要讲解了数学建模中常见的一类问题：线性规划，及其求解
                        
                    </div>
                    <div class="publish-info">
                            <span class="publish-date">
                                <i class="far fa-clock fa-fw icon-date"></i>2022-01-01
                            </span>
                        <span class="publish-author">
                            
                            <i class="fas fa-bookmark fa-fw icon-category"></i>
                            
                            <a href="/categories/%E6%95%B0%E5%AD%A6%E5%BB%BA%E6%A8%A1%E7%AE%97%E6%B3%95/" class="post-category">
                                    数学建模算法
                                </a>
                            
                            
                        </span>
                    </div>
                </div>
                
                <div class="card-action article-tags">
                    
                    <a href="/tags/Python/">
                        <span class="chip bg-color">Python</span>
                    </a>
                    
                    <a href="/tags/Math-Modeling/">
                        <span class="chip bg-color">Math Modeling</span>
                    </a>
                    
                    <a href="/tags/%E7%BA%BF%E6%80%A7%E8%A7%84%E5%88%92/">
                        <span class="chip bg-color">线性规划</span>
                    </a>
                    
                    <a href="/tags/Linear-Programming/">
                        <span class="chip bg-color">Linear Programming</span>
                    </a>
                    
                </div>
                
            </div>
        </div>
        
    </div>
</article>

</div>


<script>
    $('#articleContent').on('copy', function (e) {
        // IE8 or earlier browser is 'undefined'
        if (typeof window.getSelection === 'undefined') return;

        var selection = window.getSelection();
        // if the selection is short let's not annoy our users.
        if (('' + selection).length < Number.parseInt('120')) {
            return;
        }

        // create a div outside of the visible area and fill it with the selected text.
        var bodyElement = document.getElementsByTagName('body')[0];
        var newdiv = document.createElement('div');
        newdiv.style.position = 'absolute';
        newdiv.style.left = '-99999px';
        bodyElement.appendChild(newdiv);
        newdiv.appendChild(selection.getRangeAt(0).cloneContents());

        // we need a <pre> tag workaround.
        // otherwise the text inside "pre" loses all the line breaks!
        if (selection.getRangeAt(0).commonAncestorContainer.nodeName === 'PRE' || selection.getRangeAt(0).commonAncestorContainer.nodeName === 'CODE') {
            newdiv.innerHTML = "<pre>" + newdiv.innerHTML + "</pre>";
        }

        var url = document.location.href;
        newdiv.innerHTML += '<br />'
            + '来源: JackWang&#39;s Blog<br />'
            + '文章作者: Jack Wang<br />'
            + '文章链接: <a href="' + url + '">' + url + '</a><br />'
            + '本文章著作权归作者所有，任何形式的转载都请注明出处。';

        selection.selectAllChildren(newdiv);
        window.setTimeout(function () {bodyElement.removeChild(newdiv);}, 200);
    });
</script>


<!-- 代码块功能依赖 -->
<script type="text/javascript" src="/libs/codeBlock/codeBlockFuction.js"></script>

<!-- 代码语言 -->

<script type="text/javascript" src="/libs/codeBlock/codeLang.js"></script>


<!-- 代码块复制 -->

<script type="text/javascript" src="/libs/codeBlock/codeCopy.js"></script>


<!-- 代码块收缩 -->

<script type="text/javascript" src="/libs/codeBlock/codeShrink.js"></script>


    </div>
    <div id="toc-aside" class="expanded col l3 hide-on-med-and-down">
        <div class="toc-widget card" style="background-color: white;">
            <div class="toc-title"><i class="far fa-list-alt"></i>&nbsp;&nbsp;目录</div>
            <div id="toc-content"></div>
        </div>
    </div>
</div>

<!-- TOC 悬浮按钮. -->

<div id="floating-toc-btn" class="hide-on-med-and-down">
    <a class="btn-floating btn-large bg-color">
        <i class="fas fa-list-ul"></i>
    </a>
</div>


<script src="/libs/tocbot/tocbot.min.js"></script>
<script>
    $(function () {
        tocbot.init({
            tocSelector: '#toc-content',
            contentSelector: '#articleContent',
            headingsOffset: -($(window).height() * 0.4 - 45),
            collapseDepth: Number('2'),
            headingSelector: 'h1, h2, h3, h4, h5, h6'
        });

        // modify the toc link href to support Chinese.
        let i = 0;
        let tocHeading = 'toc-heading-';
        $('#toc-content a').each(function () {
            $(this).attr('href', '#' + tocHeading + (++i));
        });

        // modify the heading title id to support Chinese.
        i = 0;
        $('#articleContent').children('h1, h2, h3, h4, h5, h6').each(function () {
            $(this).attr('id', tocHeading + (++i));
        });

        // Set scroll toc fixed.
        let tocHeight = parseInt($(window).height() * 0.4 - 64);
        let $tocWidget = $('.toc-widget');
        $(window).scroll(function () {
            let scroll = $(window).scrollTop();
            /* add post toc fixed. */
            if (scroll > tocHeight) {
                $tocWidget.addClass('toc-fixed');
            } else {
                $tocWidget.removeClass('toc-fixed');
            }
        });

        
        /* 修复文章卡片 div 的宽度. */
        let fixPostCardWidth = function (srcId, targetId) {
            let srcDiv = $('#' + srcId);
            if (srcDiv.length === 0) {
                return;
            }

            let w = srcDiv.width();
            if (w >= 450) {
                w = w + 21;
            } else if (w >= 350 && w < 450) {
                w = w + 18;
            } else if (w >= 300 && w < 350) {
                w = w + 16;
            } else {
                w = w + 14;
            }
            $('#' + targetId).width(w);
        };

        // 切换TOC目录展开收缩的相关操作.
        const expandedClass = 'expanded';
        let $tocAside = $('#toc-aside');
        let $mainContent = $('#main-content');
        $('#floating-toc-btn .btn-floating').click(function () {
            if ($tocAside.hasClass(expandedClass)) {
                $tocAside.removeClass(expandedClass).hide();
                $mainContent.removeClass('l9');
            } else {
                $tocAside.addClass(expandedClass).show();
                $mainContent.addClass('l9');
            }
            fixPostCardWidth('artDetail', 'prenext-posts');
        });
        
    });
</script>

    

</main>


<script src="https://cdn.bootcss.com/mathjax/2.7.5/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<script>
    MathJax.Hub.Config({
        tex2jax: {inlineMath: [['$', '$'], ['\\(', '\\)']]}
    });
</script>



    <footer class="page-footer bg-color">
    

    <div class="container row center-align"
         style="margin-bottom: 15px !important;">
        <div class="col s12 m8 l8 copy-right">
            Copyright&nbsp;&copy;
            
                <span id="year">2021-2023</span>
            
            <a href="/about" target="_blank">Jack Wang</a>
            <!-- |&nbsp;Powered by&nbsp;<a href="https://hexo.io/" target="_blank">Hexo</a> -->
            <!-- |&nbsp;Theme&nbsp;<a href="https://github.com/blinkfox/hexo-theme-matery" target="_blank">Matery</a> -->
            <br>
            
                &nbsp;<i class="fas fa-chart-area"></i>&nbsp;站点总字数:&nbsp;<span
                        class="white-color">603.8k</span>
            
            
            
                
            
            
                <span id="busuanzi_container_site_pv">
                &nbsp;|&nbsp;<i class="far fa-eye"></i>&nbsp;总访问量:&nbsp;
                    <span id="busuanzi_value_site_pv" class="white-color"></span>
            </span>
            
            
                <span id="busuanzi_container_site_uv">
                &nbsp;|&nbsp;<i class="fas fa-users"></i>&nbsp;总访问人数:&nbsp;
                    <span id="busuanzi_value_site_uv" class="white-color"></span>
            </span>
            
            <br>

            <!-- 运行天数提醒. -->
            
                <span id="sitetime"> Loading ...</span>
                <script>
                    var calcSiteTime = function () {
                        var seconds = 1000;
                        var minutes = seconds * 60;
                        var hours = minutes * 60;
                        var days = hours * 24;
                        var years = days * 365;
                        var today = new Date();
                        var startYear = "2021";
                        var startMonth = "11";
                        var startDate = "12";
                        var startHour = "0";
                        var startMinute = "0";
                        var startSecond = "0";
                        var todayYear = today.getFullYear();
                        var todayMonth = today.getMonth() + 1;
                        var todayDate = today.getDate();
                        var todayHour = today.getHours();
                        var todayMinute = today.getMinutes();
                        var todaySecond = today.getSeconds();
                        var t1 = Date.UTC(startYear, startMonth, startDate, startHour, startMinute, startSecond);
                        var t2 = Date.UTC(todayYear, todayMonth, todayDate, todayHour, todayMinute, todaySecond);
                        var diff = t2 - t1;
                        var diffYears = Math.floor(diff / years);
                        var diffDays = Math.floor((diff / days) - diffYears * 365);

                        // 区分是否有年份.
                        var language = 'zh-CN';
                        if (startYear === String(todayYear)) {
                            document.getElementById("year").innerHTML = todayYear;
                            var daysTip = 'This site has been running for ' + diffDays + ' days';
                            if (language === 'zh-CN') {
                                daysTip = '本站已运行 ' + diffDays + ' 天';
                            } else if (language === 'zh-HK') {
                                daysTip = '本站已運行 ' + diffDays + ' 天';
                            }
                            document.getElementById("sitetime").innerHTML = daysTip;
                        } else {
                            document.getElementById("year").innerHTML = startYear + " - " + todayYear;
                            var yearsAndDaysTip = 'This site has been running for ' + diffYears + ' years and '
                                + diffDays + ' days';
                            if (language === 'zh-CN') {
                                yearsAndDaysTip = '本站已运行 ' + diffYears + ' 年 ' + diffDays + ' 天';
                            } else if (language === 'zh-HK') {
                                yearsAndDaysTip = '本站已運行 ' + diffYears + ' 年 ' + diffDays + ' 天';
                            }
                            document.getElementById("sitetime").innerHTML = yearsAndDaysTip;
                        }
                    }

                    calcSiteTime();
                </script>
            
            <br>
            
                <span id="icp"><img src="/medias/icp.png"
                                    style="vertical-align: text-bottom;"/>
                <a href="https://beian.miit.gov.cn" target="_blank">陕ICP备2021014294号-1</a>
            </span>
            
        </div>
        <div class="col s12 m4 l4 social-link social-statis">
    <a href="https://github.com/jackwang0108" class="tooltipped" target="_blank" data-tooltip="访问我的GitHub" data-position="top" data-delay="50">
        <i class="fab fa-github"></i>
    </a>



    <a href="mailto:2232123545@qq.com" class="tooltipped" target="_blank" data-tooltip="邮件联系我" data-position="top" data-delay="50">
        <i class="fas fa-envelope-open"></i>
    </a>







    <a href="tencent://AddContact/?fromId=50&fromSubId=1&subcmd=all&uin=2232123545" class="tooltipped" target="_blank" data-tooltip="QQ联系我: 2232123545" data-position="top" data-delay="50">
        <i class="fab fa-qq"></i>
    </a>







</div>
    </div>
</footer>

<div class="progress-bar"></div>


    <!-- 搜索遮罩框 -->
<div id="searchModal" class="modal">
    <div class="modal-content">
        <div class="search-header">
            <span class="title"><i class="fas fa-search"></i>&nbsp;&nbsp;搜索</span>
            <input type="search" id="searchInput" name="s" placeholder="请输入搜索的关键字"
                   class="search-input">
        </div>
        <div id="searchResult"></div>
    </div>
</div>

<script type="text/javascript">
$(function () {
    var searchFunc = function (path, search_id, content_id) {
        'use strict';
        $.ajax({
            url: path,
            dataType: "xml",
            success: function (xmlResponse) {
                // get the contents from search data
                var datas = $("entry", xmlResponse).map(function () {
                    return {
                        title: $("title", this).text(),
                        content: $("content", this).text(),
                        url: $("url", this).text()
                    };
                }).get();
                var $input = document.getElementById(search_id);
                var $resultContent = document.getElementById(content_id);
                $input.addEventListener('input', function () {
                    var str = '<ul class=\"search-result-list\">';
                    var keywords = this.value.trim().toLowerCase().split(/[\s\-]+/);
                    $resultContent.innerHTML = "";
                    if (this.value.trim().length <= 0) {
                        return;
                    }
                    // perform local searching
                    datas.forEach(function (data) {
                        var isMatch = true;
                        var data_title = data.title.trim().toLowerCase();
                        var data_content = data.content.trim().replace(/<[^>]+>/g, "").toLowerCase();
                        var data_url = data.url;
                        data_url = data_url.indexOf('/') === 0 ? data.url : '/' + data_url;
                        var index_title = -1;
                        var index_content = -1;
                        var first_occur = -1;
                        // only match artiles with not empty titles and contents
                        if (data_title !== '' && data_content !== '') {
                            keywords.forEach(function (keyword, i) {
                                index_title = data_title.indexOf(keyword);
                                index_content = data_content.indexOf(keyword);
                                if (index_title < 0 && index_content < 0) {
                                    isMatch = false;
                                } else {
                                    if (index_content < 0) {
                                        index_content = 0;
                                    }
                                    if (i === 0) {
                                        first_occur = index_content;
                                    }
                                }
                            });
                        }
                        // show search results
                        if (isMatch) {
                            str += "<li><a href='" + data_url + "' class='search-result-title'>" + data_title + "</a>";
                            var content = data.content.trim().replace(/<[^>]+>/g, "");
                            if (first_occur >= 0) {
                                // cut out 100 characters
                                var start = first_occur - 20;
                                var end = first_occur + 80;
                                if (start < 0) {
                                    start = 0;
                                }
                                if (start === 0) {
                                    end = 100;
                                }
                                if (end > content.length) {
                                    end = content.length;
                                }
                                var match_content = content.substr(start, end);
                                // highlight all keywords
                                keywords.forEach(function (keyword) {
                                    var regS = new RegExp(keyword, "gi");
                                    match_content = match_content.replace(regS, "<em class=\"search-keyword\">" + keyword + "</em>");
                                });

                                str += "<p class=\"search-result\">" + match_content + "...</p>"
                            }
                            str += "</li>";
                        }
                    });
                    str += "</ul>";
                    $resultContent.innerHTML = str;
                });
            }
        });
    };

    searchFunc('/search.xml', 'searchInput', 'searchResult');
});
</script>

    <!-- 回到顶部按钮 -->
<div id="backTop" class="top-scroll">
    <a class="btn-floating btn-large waves-effect waves-light" href="#!">
        <i class="fas fa-arrow-up"></i>
    </a>
</div>


    <script src="/libs/materialize/materialize.min.js"></script>
    <script src="/libs/masonry/masonry.pkgd.min.js"></script>
    <script src="/libs/aos/aos.js"></script>
    <script src="/libs/scrollprogress/scrollProgress.min.js"></script>
    <script src="/libs/lightGallery/js/lightgallery-all.min.js"></script>
    <script src="/js/matery.js"></script>

    

    
        
        <script type="text/javascript">
            // 只在桌面版网页启用特效
            var windowWidth = $(window).width();
            if (windowWidth > 768) {
                document.write('<script type="text/javascript" src="/libs/others/sakura.js"><\/script>');
            }
        </script>
    

    <!-- 雪花特效 -->
    

    <!-- 鼠标星星特效 -->
    

     
        <script src="https://ssl.captcha.qq.com/TCaptcha.js"></script>
        <script src="/libs/others/TencentCaptcha.js"></script>
        <button id="TencentCaptcha" data-appid="xxxxxxxxxx" data-cbfn="callback" type="button" hidden></button>
    

    <!-- Baidu Analytics -->

    <!-- Baidu Push -->

<script>
    (function () {
        var bp = document.createElement('script');
        var curProtocol = window.location.protocol.split(':')[0];
        if (curProtocol === 'https') {
            bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';
        } else {
            bp.src = 'http://push.zhanzhang.baidu.com/push.js';
        }
        var s = document.getElementsByTagName("script")[0];
        s.parentNode.insertBefore(bp, s);
    })();
</script>

    
    <script src="/libs/others/clicklove.js" async="async"></script>
    
    
    <script async src="/libs/others/busuanzi.pure.mini.js"></script>
    

    

    

    <!--腾讯兔小巢-->
    
    

    

    

    
    <script src="/libs/instantpage/instantpage.js" type="module"></script>
    

</body>

</html>
